//题目:
// 给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
// 由于答案可能很大，因此 返回答案模 10^9 + 7 。

// 示例 1：
// 输入：arr = [3,1,2,4]
// 输出：17
// 解释：
// 子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 
// 最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。

// 示例 2：
// 输入：arr = [11,81,94,43,3]
// 输出：444
 
// 提示：
// 1 <= arr.length <= 3 * 104
// 1 <= arr[i] <= 3 * 104
#include<iostream>
#include<vector>
#include<limits.h>

using namespace std;
//代码
class Solution 
{
public:
    int sumSubarrayMins(vector<int>& arr) 
    {
        int n=arr.size(),MAX_VALUE=1e9+7;
        //超出内存限制
        // //1.创建dp表————dp[i]表示：以arr[i]为结尾的所有子数组
        // vector<vector<vector<int>>> dp(n,vector<vector<int>>());
        // //2.初始化
        // dp[0].push_back(vector<int>(1,arr[0]));
        // cout<<dp[0].size()<<endl;
        // //3.填表————动态转移方程:dp[i].push_back(vector<int>(arr[i]));
        // for(int i=1;i<n;i++)
        // {
        //     dp[i].resize(i+1,vector<int>());
        //     dp[i]=dp[i-1];
        //     for(int j=0;j<dp[i].size();j++)
        //         dp[i][j].push_back(arr[i]);

        //     dp[i].push_back(vector<int>(1,arr[i]));
        // }
        // //4.确定返回值
        // int ret=0;
        // for(int i=0;i<n;i++)
        // {
        //     //dp[i]表示：以nums[i]为结尾的所有子数组
        //     for(int j=0;j<dp[i].size();j++)
        //     {
        //         // cout<<"{[";
        //         int min_val=INT_MAX;
        //         for(auto x:dp[i][j])
        //         {
        //             // cout<<x<<" ";
        //             min_val=min(min_val,x);
        //         }
        //         // cout<<"]},";
        //         ret+=min_val;
        //     }
        // }
        // return ret;

        //优化————仍超出内存限制
        // //1.创建dp表————dp[i][j]表示：以arr[i]为结尾的，第j个子数组中的最小值
        // vector<vector<int>> dp(n,vector<int>());
        // //2.初始化
        // dp[0].push_back(arr[0]);
        // //3.填表————动态转移方程:dp[i].push_back(vector<int>(arr[i]));
        // int ret=dp[0][0];
        // for(int i=1;i<n;i++)
        // {
        //     dp[i].resize(i+1);
        //     dp[i][0]=arr[i];//arr[i]为结尾的第一个子数组
        //     ret+=dp[i][0];
        //     for(int j=1;j<=i;j++)
        //     {
        //         dp[i][j]=min(arr[i],dp[i-1][j-1]);
        //         (ret+=dp[i][j])%=MAX_VALUE;
        //         cout<<dp[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        // //4.确定返回值
        // return ret;

        //三次优化————超时
        //1.创建dp表————dp[i][j]表示：以arr[i]为结尾的，第j个子数组中的最小值
        vector<int> dp(n);
        //2.初始化
        dp[0]=arr[0];
        //3.填表————动态转移方程:dp[i].push_back(vector<int>(arr[i]));
        int ret=dp[0];
        for(int i=1;i<n;i++)
        {
            ret+=arr[i];
            for(int j=i;j>=1;j--)
            {
                dp[j]=min(arr[i],dp[j-1]);
                (ret+=dp[j])%=MAX_VALUE;
            }
            dp[0]=arr[i];
        }
        //4.确定返回值
        return ret;
    }
};